# 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 
# 
#  每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
# 
#  注意：给定 n 是一个正整数。 
# 
#  示例 1： 
# 
#  输入： 2
# 输出： 2
# 解释： 有两种方法可以爬到楼顶。
# 1.  1 阶 + 1 阶
# 2.  2 阶 
# 
#  示例 2： 
# 
#  输入： 3
# 输出： 3
# 解释： 有三种方法可以爬到楼顶。
# 1.  1 阶 + 1 阶 + 1 阶
# 2.  1 阶 + 2 阶
# 3.  2 阶 + 1 阶
#  
#  Related Topics 动态规划 
#  👍 1617 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def climbStairs(self, n: int) -> int:
        x_2 = 0
        x_1 = 0
        x = 1
        for i in range(n):
            x_2 = x_1
            x_1 = x
            x = x_2 + x_1
        return x



# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


"""
f(x) = f(x-1) + f(x-2)
爬到x的方案数 = 爬到x-1 的方案数和 x-2的方案数之和
f(0) = 1, f(1) = 1, f(2) = 2
"""

# def climbStairs(self, n: int) -> int:
#     x_2 = 0
#     x_1 = 0
#     x = 1
#     for i in range(n):
#         x_2 = x_1
#         x_1 = x
#         x = x_1 + x_2
#     return x
if __name__ == '__main__':
    s = Solution()
    result = s.climbStairs(3)
    assert result == 3, result
    result1 = s.climbStairs(1)
    assert result1 == 1, result1
